﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;

//地下城游戏
//https://leetcode.cn/problems/dungeon-game/
//class Solution {
//public:
//    int calculateMinimumHP(vector<vector<int>>& dungeon) {
//        int m = dungeon.size();
//        int n = dungeon[0].size();
//        vector<vector<int>> vv(m + 1, vector<int>(n + 1, INT_MAX));
//        vv[m - 1][n] = 1;
//        vv[m][n - 1] = 1;
//        for (int i = m - 1; i >= 0; --i)
//            for (int k = n - 1; k >= 0; --k)
//            {
//                //x+dungeon[i][k]>=vv[i+1][k] //x+dungeon[i][k]>=vv[i][k+1] 两者最小值
//                vv[i][k] = min(vv[i + 1][k], vv[i][k + 1]) - dungeon[i][k];
//                vv[i][k] = max(1, vv[i][k]); //如果前面是个大血包则初始值为1即可
//            }
//        return vv[0][0];
//    }
//};

//面试题17.16.按摩币
// https://leetcode.cn/problems/the-masseuse-lcci/
// 打家劫舍
// https://leetcode.cn/problems/house-robber/
//class Solution {
//public:
//    int massage(vector<int>& nums) {
        //int n = nums.size();
        //if (n == 0) return 0;
        //if (n == 1) return nums[0];

        //vector<int> f(n); //选择i时的最大值
        //vector<int> g(n); //不选择i时最大值
        //f[0] = nums[0]; //第一个值必选则为初始值 第一个值不选则g[0]=0
        //for (int i = 1; i < n; ++i)
        //{
        //    f[i] = g[i - 1] + nums[i]; //选择这个位置那么一定是不选上一个位置
        //    g[i] = max(f[i - 1], g[i - 1]); //不选当前位置则这个位置的上一个位置即可以选也可以不选求两者的最大值
        //}
        //return max(f[n - 1], g[n - 1]); //返回选最后一个值和不选的最大值
//    }
//};


//打家劫舍2
//https://leetcode.cn/problems/house-robber-ii/
//class Solution {
//public:
//    int rob1(const vector<int>& nums, int left, int right)
//    {
//        if (left > right) return 0;
//        int n = nums.size();
//        vector<int> f(n);
//        vector<int> g(n);
//        f[left] = nums[left];
//        for (int i = left; i <= right; ++i)
//        {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[right], g[right]);
//    }
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 0) return 0;
//        if (n == 1) return nums[0];
//        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1)); //分别为偷第一个和不偷第一个时的情况
//    }
//};